
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Arrays;

class Node implements Comparable<Node> {
	public int[][] state;
	public String[] actions;
	public int cost;

	Node(int[][] state, String[] actions, int cost) {
		this.state = state;
		this.actions = actions;
		this.cost = cost;
	}

	int[] find_zero_ij() {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (this.state[i][j] == 0) {
					int[] temp = { i, j };
					return temp;
				}
			}
		}
		return null;
	}

	public int[][] copyState(){
		int[][] a = new int[3][3];
		for (int i = 0; i < 3; i++){
			for (int j = 0; j < 3; j++){
				a[i][j] = this.state[i][j];
			}
		}
		return a;
	}
	
	public void prnt(){
		System.out.println(Arrays.toString(this.state[0]));
		System.out.println(Arrays.toString(this.state[1]));
		System.out.println(Arrays.toString(this.state[2]));
		System.out.println();
	}

	public int compareTo(Node o) {
		// used for sort
		return this.cost - o.cost;
	}
}


public class Astar8Puzzle {
	// 初始状态
	 static int[][] start_state = { { 7, 2, 4 }, { 5, 0, 6 }, { 8, 3, 1 } };
//	 static int[][] start_state = { {4, 0, 5}, {1, 2, 3}, {7, 8, 6}};
	// 目标状态
	static int[][] end_state = { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 } };

	static int h1(int[][] node_state, int[][] end_state) {
		int cost = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (node_state[i][j] != end_state[i][j]) {
					cost += 1;
				}
			}
		}
		return cost;
	}

	static int h2(int[][] node_state, int[][] end_state) {
		int cost = 0;
		
		// TODO
		
		return cost;
	}
	
	static boolean isSame(int[][] s1, int[][] s2){
		boolean same = true;
		for (int m = 0; m < s1.length; m++) {
			for (int k = 0; k < s1[0].length; k++) {
				if (s1[m][k] != s2[m][k]) {
					same = false;
					break;
				}
			}
		}
		return same;
	}
	
	static boolean hasNotState(int[][] s, ArrayList<int[][]> c){
		boolean has_not = true;
		for (int i = 0; i < c.size(); i++) {
			if (isSame(s, c.get(i))){
				has_not = false;
				break;
			}
		}
		return has_not;
	}

	static Node move(Node node, String action) {
		Node next_node = null;
		int[][] state = node.copyState();
		int[] temp = node.find_zero_ij();
		int i = temp[0];
		int j = temp[1];
		boolean has_next = false;
		if ((action == "Up") && (i - 1 >= 0)) {
			state[i][j] = state[i - 1][j];
			state[i - 1][j] = 0;
			has_next = true;
		}else if ((action == "Down") && (i + 1 <= 2)) {
			state[i][j] = state[i + 1][j];
			state[i + 1][j] = 0;
			has_next = true;
		}else if ((action == "Left") && (j - 1 >= 0)) {
			state[i][j] = state[i][j-1];
			state[i ][j-1] = 0;
			has_next = true;
		}else if ((action == "Right") && (j + 1 <= 2)) {
			state[i][j] = state[i][j+1];
			state[i ][j+1] = 0;
			has_next = true;
		}

		// TODO 'Down'
    // TODO 'Left'
    // TODO 'Right'
		
		if (has_next) {
			String[] actions = node.actions;
			int action_length = actions == null ? 0 : actions.length;

			String[] new_actions = new String[action_length + 1];
			for (int k = 0; k < action_length; k++) {
				new_actions[k] = actions[k];
			}
			new_actions[action_length] = action;
			int cost = h2(state, end_state) + new_actions.length;
			next_node = new Node(state, new_actions, cost);
		}
		return next_node;
	}

	static Node a_star() {
		Node start_node = new Node(start_state, null, 0 + h2(start_state, end_state));
		Node end_node = null;
		String[] option = { "Up", "Down", "Left", "Right" };

		ArrayList<int[][]> closed = new ArrayList<int[][]>();
		// 优先队列
		PriorityQueue<Node> fringe = new PriorityQueue<Node>();
		
		fringe.add(start_node);
		int n = 0;
		while (fringe.size() > 0) {
			Node current_node = fringe.poll();
			
			// TODO Is end state? You can call isSame(...) for this.
			
			for (int i = 0; i < 4; i++) {
				// TODO call move(...) to get next_node by each action
				if (next_node != null &&  hasNotState(next_node.state, closed)) {
					// TODO 入队列
				}
			}
			closed.add(current_node.state);

			n += 1;
			if (n % 10000 == 0) {
				System.out.println("n=" + n + ",current_node.getCost=" + current_node.cost);
			}
			if (n >= 100000) {
				System.out.println("Do not find resolution after searching 100000 nodes ...");
			}
		}
		// print actions
		Node next_node = start_node;
		System.out.println("Initial state");
		next_node.prnt();

		for (int i = 0; i < end_node.actions.length; i++) {
			next_node = move(next_node, end_node.actions[i]);
			System.out.println(end_node.actions[i]);
			next_node.prnt();
		}
		System.out.println(n + ":" + end_node.actions.length + ":" + Arrays.toString(end_node.actions));
		return end_node;
	}

	public static void main(String[] args) {
		Astar8Puzzle.a_star();
	}
}
